import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Graphics;
import javax.swing.Box;
import javax.swing.BoxLayout;
import javax.swing.JButton;
import javax.swing.JLabel;
import javax.swing.JPanel;
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import java.util.concurrent.atomic.AtomicBoolean;

@SuppressWarnings("serial")
public class BinaryTreePanel extends JPanel {
	
	private ArrayList<LabeledRectangle> theArray;

	private JPanel CenterPanel, WorkPanel,HelpPanel;	
	
	private JButton findMinButton,
					findMaxButton,
					searchButton,
					stepButton,
					resetButton;
	
	private JLabel ErrorLabel;
	
	private final int MAX_ARRAY_SIZE = 15;
	private final int ARRAY_START_Y = 35;
	private final int ARRAY_START_X = 8;
	private final int NODE_WIDTH = 50;
	private final int NODE_HEIGHT = 50;
	private final int NODE_SPACER = 8;
	private final int HENNINGER_CONSTANT = 870;	
	private Thread bstThread;
	private AtomicBoolean paused; 
	
	private final Color NODE_COLOR = new Color(0x00746b);
	private final Font LabelFont = new Font("Dialog", 1, 14);
	
	private IntegerField userInputValue;
	
	// draw the binary tree panel consisting of a control, workspace, and help panel. 
	public BinaryTreePanel()
	{
		
		paused = new AtomicBoolean(true); // atomic boolean object to synchronize the bst thread
		
		theArray = new ArrayList<LabeledRectangle>();
		
		createArray(MAX_ARRAY_SIZE);

		WorkPanel = new JPanel();
		HelpPanel = new JPanel();
		CenterPanel = new JPanel();
		
		this.setBackground(Color.white);
		WorkPanel.setBackground(Color.white);
		WorkPanel.setLayout(null);

		HelpPanel.setPreferredSize(new Dimension(0, 75));
		HelpPanel.setLayout(new BoxLayout(HelpPanel, BoxLayout.Y_AXIS));
		
		JLabel HelpLabel = new JLabel("A sorted array can be turned into a BST by  recursively splitting it into two halves on either side of its middle value.");
		
		HelpLabel.setFont(LabelFont);
		HelpLabel.setForeground(Color.black);
		HelpLabel.setAlignmentX(CENTER_ALIGNMENT);

		JLabel HelpLabel1 = new JLabel("Use the Step Through button to watch the tree grow. Try finding some values to see how the tree is traversed.");	
		HelpLabel1.setFont(LabelFont);
		HelpLabel1.setForeground(Color.black);
		HelpLabel1.setAlignmentX(CENTER_ALIGNMENT);

		ErrorLabel = new JLabel();	
		ErrorLabel.setFont(LabelFont);
		ErrorLabel.setForeground(Color.red);
		ErrorLabel.setAlignmentX(CENTER_ALIGNMENT);

		HelpPanel.add(HelpLabel);
		HelpPanel.add(HelpLabel1);
		HelpPanel.add(Box.createRigidArea(new Dimension(0,10)));
		HelpPanel.add(ErrorLabel);

		BorderLayout blayout2 = new BorderLayout();
		blayout2.setHgap(3);
		blayout2.setVgap(3);

		CenterPanel.setLayout(blayout2);
		CenterPanel.add(WorkPanel, BorderLayout.CENTER);
		CenterPanel.add(HelpPanel, BorderLayout.SOUTH);

		BorderLayout blayout = new BorderLayout();
		blayout.setHgap(3);
		blayout.setVgap(3);

		this.setLayout(blayout);
		this.add(CenterPanel, BorderLayout.CENTER);
		this.add(ControlPanel(), BorderLayout.EAST);
		
		// create a runnable thread so that stepping through the tree creation is intuitive
		Runnable runnable = new Runnable()        
		{

			private boolean bstStep(LabeledRectangle parent, int start, int end, int leftLimit, int rightLimit, int newY, int level)
			{
				if (start > end)
					return false;

				if(paused.get())
				{

					if (allDrawn())
					{
						stepButton.setEnabled(false);
						searchButton.setEnabled(true);
						findMinButton.setEnabled(true);
						findMaxButton.setEnabled(true);
						resetButton.setEnabled(true);
						
					}

					synchronized(bstThread)
					{
						try 
						{
							bstThread.wait();
						} 
						catch (InterruptedException e) 
						{
						}
					}
				}

				int mid = start + (end - start) / 2;

				LabeledRectangle thisNode = theArray.get(mid);

				thisNode.setColor(Color.red);
				repaint();

				try {
					Thread.sleep(500);
				} catch (InterruptedException e1) {
					e1.printStackTrace();
				}
				
				if (parent != null)
				{		
					if (thisNode.compareTo(parent) < 0) // left node
						parent.left = thisNode;
					else if (thisNode.compareTo(parent) > 0) // right node
						parent.right = thisNode;
				
				}	
			
				int newX = ARRAY_START_X + leftLimit + (rightLimit - leftLimit) / 2 - (NODE_WIDTH + NODE_SPACER) / 2; 	
				thisNode.x = newX;
				thisNode.y = newY + NODE_HEIGHT/2;   
				thisNode.level = level;
				thisNode.drawn = true;        

				repaint();

				try {
					Thread.sleep(500);
				} catch (InterruptedException e1) {
					e1.printStackTrace();
				}

				thisNode.setColor(NODE_COLOR);

				repaint();

				paused.set(true);

				// call the function, unless we're a leaf node
				if (start == end)
				{
					return true;
				}

				bstStep(thisNode, start, mid - 1, leftLimit, newX + NODE_WIDTH, thisNode.y + (NODE_HEIGHT + 20), level+1);
				bstStep(thisNode, mid + 1, end, newX, rightLimit, thisNode.y + (NODE_HEIGHT + 20), level+1);

				return true;

			}

			public void run() 
			{

				while (true)
				{    
					LabeledRectangle lr = theArray.get((theArray.size() - 1) / 2);

					bstStep(null, 0, theArray.size() - 1, 0, 870, lr.y, 0);   
				}

			}
		};
		
		bstThread = new Thread(runnable);
		bstThread.start();

	}

	// the control panel to display on the right side of the page with
	// options related to binary trees - findMin, findMax, Step, and Search
	public JPanel ControlPanel() {
		
		JPanel thisPanel = new JPanel();
		thisPanel.setPreferredSize(new Dimension(200, 0));
		thisPanel.setLayout(new BoxLayout(thisPanel, BoxLayout.Y_AXIS));
		
		JLabel bubbleSortLabel = new JLabel("Binary Tree Operations");
		
		bubbleSortLabel.setFont(LabelFont);
		
		findMaxButton = new JButton("Find Maximum");
		stepButton = new JButton("Step Through");
		findMinButton = new JButton("Find Minimum");
		searchButton = new JButton("Search");
		resetButton = new JButton("Reset");
		userInputValue = new IntegerField();
		
		// add action listeners to the buttons
		ActionEventHandler aeh = new ActionEventHandler();
		findMaxButton.addActionListener(aeh);
		stepButton.addActionListener(aeh);
		findMinButton.addActionListener(aeh);
		searchButton.addActionListener(aeh);
		resetButton.addActionListener(aeh);
		
		bubbleSortLabel.setAlignmentX(CENTER_ALIGNMENT);
		findMaxButton.setAlignmentX(CENTER_ALIGNMENT);
		stepButton.setAlignmentX(CENTER_ALIGNMENT);
		findMinButton.setAlignmentX(CENTER_ALIGNMENT);
		searchButton.setAlignmentX(CENTER_ALIGNMENT);
		resetButton.setAlignmentX(CENTER_ALIGNMENT);
		
		thisPanel.add(Box.createRigidArea(new Dimension(0,10)));
		thisPanel.add(bubbleSortLabel);
		thisPanel.add(Box.createRigidArea(new Dimension(0,10)));
		thisPanel.add(stepButton);
		thisPanel.add(findMaxButton);
		thisPanel.add(findMinButton);
		thisPanel.add(Box.createRigidArea(new Dimension(0,10)));
		thisPanel.add(userInputValue);
		thisPanel.add(Box.createRigidArea(new Dimension(0,10)));
		thisPanel.add(searchButton);
		thisPanel.add(Box.createRigidArea(new Dimension(0,10)));
		thisPanel.add(resetButton);
		thisPanel.add(Box.createRigidArea(new Dimension(0,350)));

		findMaxButton.setEnabled(false);
		findMinButton.setEnabled(false);
		searchButton.setEnabled(false);
		resetButton.setEnabled(false);
		
		return thisPanel;
	}
		
	// fill our array for the binary tree
	public void createArray(int size)
	{
		int startX = ARRAY_START_X;
		ArrayList<Integer> nums = new ArrayList<Integer>();
		
		// populate an array with unique items
		for (int i = 0; i < size; i++)
		{		
			int rand = new Random().nextInt(100);
			
			while (nums.contains(rand))
				rand = new Random().nextInt(100);
			
			nums.add(rand);		
		}
		
		Collections.sort(nums);
	
		// populate the array with random items so that they can be sorted
		for (int i = 0; i < size; i++)
		{	
			theArray.add(new LabeledRectangle(startX, ARRAY_START_Y, NODE_WIDTH, NODE_HEIGHT, NODE_COLOR, "" + nums.get(i) + ""));
			startX += NODE_WIDTH + NODE_SPACER;	
		}	

	}

	// this function is used in bstStep to determine if all of the array nodes have been drawn in the tree
	// so that step execution will stop
	private boolean allDrawn()
	{		
		for (int i = 0; i < theArray.size(); i++)
		{		
			if (!theArray.get(i).drawn)
				return false;		
		}
		
		return true;	
	}
	
	// recursive workhorse to find the value at the current "root", not necessarily the tree root
    private boolean findValue(LabeledRectangle value, LabeledRectangle root)
    {
        
    	if (root == null)
    	{
    		return false;
    	}
    	
    	int compare = value.compareTo(root);  	
    	root.setColor(Color.red);
    	
    	// delay execution to display the node being compared
		try {
			Thread.sleep(800);
		} catch (InterruptedException e1) {
			e1.printStackTrace();
		}
		
		root.setColor(NODE_COLOR);
		
		repaint();
    	
		// depending on the comparison, traverse down the left or right node, or return if found
        if( compare < 0 )
            return findValue( value, root.left );   
        else if( compare > 0 )
            return findValue( value, root.right);      
        else
            return true; // the value was found
    }
    
    // the initiator for the recursive findValue function
	public boolean findValue(LabeledRectangle value)
	{
		// since we are starting from a sorted array, the middle value is the root where we can begin the search
		int mid = (theArray.size() - 1) / 2;	
		theArray.get(mid).setColor(Color.red);		
		repaint();
		
		return findValue(value, theArray.get(mid));	// call the recursive workhorse
		
	}
	
	public void paint(Graphics g) {
			
		super.paint(g);

		// draw the lines connecting the nodes
		for (int i = 0; i < theArray.size(); i++)
			theArray.get(i).drawLines(g);
		
		// draw the array nodes
		for (int i = 0; i < theArray.size(); i++)
			theArray.get(i).draw(g);
		
	}

	private class ActionEventHandler implements ActionListener {

		public void actionPerformed(ActionEvent e) {

			ErrorLabel.setText(""); // reset the error label when a button is pressed
			
			if (e.getSource() == stepButton) // step through to place the next array node in the tree
			{
				
				paused.set(false);
				
                synchronized(bstThread)
                {
                    bstThread.notify(); // wake the thread if unpaused
                }
				
			}
			else if (e.getSource() == findMinButton) // search the tree for the minimum value
			{
				
				new Thread(new Runnable() {  
				    public void run() {
				    	findValue(theArray.get(0));
				    	ErrorLabel.setText("The minimum value is " + theArray.get(0).getText());
				    }
				}).start();
				
			}
			else if (e.getSource() == findMaxButton) // search the tree for the maximum value
			{		
				new Thread(new Runnable() {  
				    public void run() { 
				    	findValue(theArray.get(theArray.size()-1));
				    	ErrorLabel.setText("The maximum value is " + theArray.get(theArray.size() - 1).getText());
				    }
				}).start();
				
			}
			else if (e.getSource() == searchButton) // search the tree for the use input value
			{
				
				new Thread(new Runnable() {  
				    public void run() { 
					    if (userInputValue.getText().length() > 0) // can't search for an empty string
					    {
				    		LabeledRectangle lr = new LabeledRectangle(0,0,0,0,null,userInputValue.getText());	    	
					    	if (findValue(lr))
					    		ErrorLabel.setText("Found the number " + lr.getText() + "!");
					    	else
					    		ErrorLabel.setText("Unable to find the number " + lr.getText() + "!");
					    }
				    }
				}).start();
				
			}	
			else if (e.getSource() == resetButton)
			{
				findMinButton.setEnabled(false);
				findMaxButton.setEnabled(false);
				searchButton.setEnabled(false);
				stepButton.setEnabled(true);
				userInputValue.setText("");
				resetButton.setEnabled(false);
				theArray.clear();
				createArray(MAX_ARRAY_SIZE);
				repaint();
			}
		}
		
	}
}
